#!/usr/bin/env python3

"""
Given an array of non-negative integers, you are initially positioned at 
the first index of the array. Each element in the array represents your 
maximum jump length at that position. 

your goal is to reach the last index in the minimum number of jumps.

Input: [2, 3, 1, 1, 4]
Output: 2
"""

class Solution:
    def jump(self, nums):
        records = None
        for index, val in enumerate(nums):
            target_index = index + val
            if records is None:
                records = [(target_index, index)]
                nums[0] = -1
            else:
                last_record = records[-1]
                first_record = records[0]
                if target_index > last_record[0]:
                    records.append((target_index, index))
                nums[index] = first_record[1]
                if first_record[0] == index:
                    records.remove(first_record)
        jumps = 0
        index = len(nums) -1
        while nums[index] != -1:
            index = nums[index]
            jumps += 1
        return jumps
        
if __name__ == '__main__':
    s = Solution()
    assert 2 == s.jump([7, 0, 9, 6, 9, 6, 1, 7, 9, 0, 1, 2, 9, 0, 3])
    assert 2 == s.jump([2, 3, 1, 1, 4])
    assert 0 == s.jump([0])
    input = [1] * 100_000_000
    print(str(s.jump(input)))
